package hardware;

import java.util.Arrays;

/**
 * The class representing the L1 Cache
 * 
 */
public class L1Cache {
	private String writePolicy;
	private int cycles;
	private int m, s, l;
	private static CacheEntry[][] dCache;
	private static CacheEntry[][] iCache;
	private L2Cache l2;
	private L3Cache l3;
	private int memAddSize;
	private int disp;
	final static String NOT_FOUND = "not found l1";
	final static String WRITE_BACK = "Write Back";
	final static String WRITE_THROUGH = "Write Through";
	
	static int hit, accessTimes = 1;
	static int hitI, accessTimesI = 1;
	static int missI = 1;
	static int miss = 1;


	public L1Cache(String wp, int c, int s, int l, int m) {
		writePolicy = wp;
		cycles = c;
		this.s = s;
		this.l = l;
		this.m = m;
		this.disp = (Log.log(l / 16));
		dCache = new CacheEntry[s / 2 / l][l / 16];
		iCache = new CacheEntry[s / 2 / l][l / 16];
	}

	/**
	 * Read hit from L1 Cache, throws exception NOT_FOUND if not found in L1
	 * Cache, to be handled then by the Cache class to perform cache miss on L1/
	 * 
	 * @param address
	 *            the address to read from
	 * @param currentTime
	 *            the current time at which the operation is performed.
	 * @return the value from the cache
	 * @throws Exception
	 *             if the the address is not found in the cache.
	 */
	public int readFromCache(int address, long currentTime) throws Exception {
		accessTimes++;
		int baseAdress = (int) (address - address % Math.pow(2, disp));
		for (int i = 0; i < dCache.length; i++) {
			if (dCache[i] != null) {
				if (dCache[i][0] != null && dCache[i][0].check(baseAdress)) { // Found
					for (int j = 0; j < dCache[i].length; j++) {
						dCache[i][j].setTimeInCache(currentTime);
					}
					hit++;
					return dCache[i][address - baseAdress].getValue();
				}
			}
		}
		miss++;
		throw new Exception(NOT_FOUND, new Throwable());
	}

	/**
	 * Read hit from L1 Cache, throws exception NOT_FOUND if not found in L1
	 * Cache, to be handled then by the Cache class to perform cache miss on L1/
	 * 
	 * @param address
	 *            the address to read from
	 * @param currentTime
	 *            the current time at which the operation is performed.
	 * @return the instruction from the cache
	 * @throws Exception
	 *             if the the address is not found in the cache.
	 */
	public Instruction readFromICache(int address, long currentTime)
			throws Exception {
		accessTimesI++;
		int baseAdress = (int) (address - address % Math.pow(2, disp));
		for (int i = 0; i < iCache.length; i++) {
			if (iCache[i] != null) {
				if (iCache[i][0] != null && iCache[i][0].check(baseAdress)) { // Found
					for (int j = 0; j < iCache[i].length; j++) {
						iCache[i][j].setTimeInCache(currentTime);
					}
					hitI++;
					return iCache[i][address - baseAdress].getInstruction();
				}
			}
		}
		missI++;
		throw new Exception(NOT_FOUND, new Throwable());
	}

	/**
	 * Read miss in L1 Cache, which get the value from the memory and updates
	 * the L1 Cache (This is called only if one level cache).
	 * 
	 * @param address
	 *            the address of the value to be read from the memory.
	 * @param currentTime
	 *            the time at which the operation is performed
	 * @return the value read from the memory.
	 */
	public int readMiss(int address, long currentTime) {
		int baseAddress = (int) (address - address % Math.pow(2, disp)); // The
																			// base
																			// address
																			// is
																			// modified
																			// in
																			// the
																			// code
																			// below
		int[] value = new int[l / 16];
		for (int i = 0; i < value.length; i++)
			value[i] = Memory.load(baseAddress + i);
		int temp = baseAddress; // Stored in temp value to be used as the
								// original base address
		if (m == 1) {
			int disp = (Log.log(l / 16));
			baseAddress = (int) (baseAddress / Math.pow(2, disp));
			int index = baseAddress % (s / l);
			if (writePolicy.equals(WRITE_BACK)) {
				if (dCache[index][0] != null) {
					if (dCache[index][0].isDirty()) {
						for (int i = 0; i < s / l; i++) {
							Memory.store(dCache[index][i].getAddress(),
									dCache[index][i].getValue());
						}
					}
				}
			}
			addToCache(index, temp, value, currentTime);
			return value[address - temp];
		} else if (m == s / l) {
			for (int i = 0; i < dCache.length; i++) {
				if (dCache[i][0] == null) {
					addToCache(i, temp, value, currentTime);
					return value[address - temp];
				}
			}
			int index = LRU();
			if (writePolicy.equals(WRITE_BACK)) {
				if (dCache[index][0].isDirty()) {
					for (int i = 0; i < s / l; i++) {
						Memory.store(dCache[index][i].getAddress(),
								dCache[index][i].getValue());
					}
				}
			}
			addToCache(index, temp, value, currentTime);
			return value[address - temp];
		} else {
			baseAddress = (int) (baseAddress / Math.pow(2, disp));
			int index = baseAddress % (s / l / m);
			for (; index < dCache.length; index += (s / l / m)) {
				if (dCache[index][0] == null) {
					addToCache(index, temp, value, currentTime);
					return value[address - temp];
				}
			}
			index = baseAddress % (s / l / m);
			int newIndex = setAssociativeLRU(index);
			if (writePolicy.equals(WRITE_BACK)) {
				if (dCache[newIndex][0].isDirty()) {
					for (int i = 0; i < s / l; i++) {
						Memory.store(dCache[newIndex][i].getAddress(),
								dCache[newIndex][i].getValue());
					}
				}
			}
			addToCache(newIndex, temp, value, currentTime);
			return value[address - temp];
		}

	}

	/**
	 * Writes to the cache using write back policy
	 * 
	 * @param address
	 *            the address to write in the memory
	 * @param value
	 *            the value to be written
	 * @param currentTime
	 *            the current time at which the operation is performed
	 * @param index
	 *            the line number in the cache in which the value should be
	 *            written
	 */
	private void writeBack(int address, int value, long currentTime, int index) {
		int i = 0;
		int size = l / 16;
		for (; i < size; i++) {
			dCache[index][i].setDirty(true);
			dCache[index][i].setTimeInCache(currentTime);
			if (dCache[index][i].getAddress() == address)
				dCache[index][i].setValue(value);
		}
	}

	/**
	 * Writes to the cache using write through policy
	 * 
	 * @param address
	 *            the address to write in the memory
	 * @param value
	 *            address the address to write in the memory
	 * @param currentTime
	 *            the current time at which the operation is performed
	 * @param index
	 *            the line number in the cache in which the value should be
	 *            written
	 */
	private void writeThrough(int address, int value, long currentTime,
			int index) {
		int i = 0;
		int size = s / l;

		for (; i < size; i++) {
			dCache[index][i].setTimeInCache(currentTime);
			if (dCache[index][i].getAddress() == address) {
				dCache[index][i].setValue(value);
				updateMemoryAndCaches(index, i, currentTime);
			}
		}
	}

	/**
	 * Write to the cache using the above methods, depending on the policy and
	 * whether the value is found or not.
	 * 
	 * @param address
	 *            the address to write in the memory
	 * @param value
	 *            address the address to write in the memory
	 * @param currentTime
	 *            the current time at which the operation is performed
	 * @param instruction
	 *            the instruction that performs the action
	 * @throws Exception
	 */
	public void writeToCache(int address, int value, long currentTime,
			Instruction instruction) throws Exception {
		accessTimes++;
		int baseAdress = (int) (address - address % Math.pow(2, disp));
		int index = 0;
		boolean found = false;
		instruction.setCacheStartTime(currentTime);
		for (int i = 0; i < dCache.length; i++) {
			if (dCache[i] != null) {
				if (dCache[i][0] != null && dCache[i][0].check(baseAdress)) { // Found
					for (int j = 0; j < dCache[i].length; j++) {
						dCache[i][j].setTimeInCache(currentTime);
					}
					index = i;
					found = true;
					break;
				}
			}
		}

		if (found) {
			hit++;
			if (writePolicy.equals(WRITE_BACK))
				writeBack(address, value, currentTime, index);
			else
				writeThrough(address, value, currentTime, index);
				instruction.setCacheEndTime(currentTime + cycles);
		} else {
			miss++;
			if (writePolicy.equals(WRITE_BACK)) {
				if (l2 != null) {
					try {
						l2.readFromCache(address, currentTime);
						instruction.setCacheEndTime(currentTime + cycles+ l2.getCycles());
					} catch (Exception e) {
						if (l3 == null) {
							l2.readMiss(address, currentTime);
							instruction.setCacheEndTime(currentTime + cycles
									+ l2.getCycles() + Memory.getAccessTime());
						} else {
							try {
								l3.readFromCache(address, currentTime);
								instruction.setCacheEndTime(currentTime
										+ cycles + l2.getCycles()
										+ l3.getCycles());
							} catch (Exception e1) {
								l3.readMiss(address, currentTime);
								instruction.setCacheEndTime(currentTime
										+ cycles + l2.getCycles()
										+ l3.getCycles()
										+ Memory.getAccessTime());
							}
						}
					}
				} else {
					readMiss(address, currentTime);
					instruction.setCacheEndTime(currentTime + cycles
							+ Memory.getAccessTime());
				}
				index = getIndex(address);
				if (index == -1)
					throw new Exception(NOT_FOUND);
				writeBack(address, value, currentTime, index);
			} else {
				updateMemoryAndCaches2(instruction, address, value, currentTime);
			}

		}
	}

	/**
	 * Updates the memory and caches with the given
	 * 
	 * @param instruction
	 * @param address
	 * @param value
	 * @param currentTime
	 */
	private void updateMemoryAndCaches2(Instruction instruction, int address,
			int value, long currentTime) {
		Memory.store(address, value);
		boolean flag2 = false;
		boolean flag3 = false;
		if (l2 != null) {
			if (l2.updateValue(address, value, currentTime)) {
				flag2 = true;
			}
		}
		if (l3 != null) {
			if (l3.updateValue(address, value, currentTime)) {
				flag3 = true;
			}
		}
		if (flag2) {
			instruction.setCacheEndTime(currentTime + l2.getCycles());
		} else if (flag3) {
			instruction.setCacheEndTime(currentTime + l3.getCycles());
		} else {
			instruction.setCacheEndTime(currentTime + Memory.getAccessTime());
		}
	}

	/**
	 * Gets the place in the cache for the given address.
	 * 
	 * @param address
	 *            the address to get the index for.
	 * @return the place in the cache for the given address.
	 */
	private int getIndex(int address) {
		int baseAddress = (int) (address - address % Math.pow(2, disp));
		int i = 0;
		for (; i < dCache.length; i++) {
			if (dCache[i][0] != null)
				if (dCache[i][0].getAddress() == baseAddress)
					return i;
		}
		return -1;
	}

	/**
	 * Adds the list of values in the cache. The line contains multiple words.
	 * 
	 * @param index
	 * @param baseAddress
	 * @param value
	 * @param currentTime
	 */
	private void addToCache(int index, int baseAddress, int[] value,
			long currentTime) {
		int size = l / 16;
		dCache[index] = new CacheEntry[size];
		for (int i = 0; i < size; i++) {
			dCache[index][i] = new CacheEntry(baseAddress + i, value[i],
					currentTime);
		}
	}

	/**
	 * Adds the list of instructions in the cache. The line contains multiple
	 * words.
	 * 
	 * @param index
	 * @param baseAddress
	 * @param value
	 * @param currentTime
	 */
	private void addToICache(int index, int baseAddress,
			Instruction[] instruction, long currentTime) {
		int size = l / 16;
		iCache[index] = new CacheEntry[size];
		for (int i = 0; i < size; i++) {
			iCache[index][i] = new CacheEntry(baseAddress + i, instruction[i],
					currentTime);
		}
	}

	/**
	 * Gets the index of the least recently used word in certain line in the
	 * cache.
	 * 
	 * @param index
	 *            the line to which the check is made.
	 * @return the place of the word in the line with least recently value.
	 */
	private int setAssociativeLRU(int index) {
		long minSoFar = dCache[index][0].getTimeInCache();
		int newIndex = index;
		for (; index < dCache.length; index += (s / l / m)) {
			if (dCache[index][0].getTimeInCache() < minSoFar) {
				minSoFar = dCache[index][0].getTimeInCache();
				newIndex = index;
			}
		}
		return newIndex;
	}

	
	private int setAssociativeLRUI(int index) {
        long minSoFar= iCache[index][0].getTimeInCache();
        int newIndex = index;
        for(;index<iCache.length;index+=(s/l/m)){
        	if(iCache[index][0].getTimeInCache()<minSoFar){
        		minSoFar = iCache[index][0].getTimeInCache();
        		newIndex = index;
        	}
        }
		return newIndex;
	}
	

	/**
	 * Updates the value in L1 cache from L2 cache. Used when read miss happens
	 * in L2 cache or L3 cache.
	 * 
	 * @param address
	 *            the address used to read.
	 * @param baseAddress2
	 *            the base address of the address in L2 cache.
	 * @param values
	 *            the values to be updated by. Returned from L2 cache.
	 * @param currentTime
	 *            the current time the operation is performed.
	 */
	public void updateFromL2Cache(int address, int baseAddress2,
			CacheEntry[] values, long currentTime) {
		int baseAddress = (int) (address - address % Math.pow(2, disp)); // The
																			// base
																			// address
																			// is
																			// modified
																			// in
																			// the
																			// code
																			// below
		int temp = baseAddress; // Stored in temp value to be used as the
								// original base address
		if (m == 1) {
			int disp = (Log.log(l / 16));
			baseAddress = (int) (baseAddress / Math.pow(2, disp));
			int index = baseAddress % (s / l);
			if (writePolicy.equals(WRITE_BACK)) {
				if (dCache[index][0] != null) {
					if (dCache[index][0].isDirty()) {
						for (int i = 0; i < l / 16; i++) {
							updateMemoryAndCaches(index, i, currentTime);
						}
					}
				}
			}
			int deltaAddress = temp - baseAddress2;
			int[] value = new int[(l / 16)];
			for (int i = deltaAddress; i < deltaAddress + (l / 16); i++) {
				value[i - deltaAddress] = values[i].getValue();
			}
			addToCache(index, temp, value, currentTime);
			return;
		} else if (m == s / l) {
			for (int i = 0; i < dCache.length; i++) {
				if (dCache[i][0] == null) {
					int deltaAddress = temp - baseAddress2;
					int[] value = new int[(l / 16)];
					for (int j = deltaAddress; j < deltaAddress + (l / 16); j++) {
						value[j - deltaAddress] = values[j].getValue();
					}
					addToCache(i, temp, value, currentTime);
					return;
				}
			}
			int index = LRU();
			if (writePolicy.equals(WRITE_BACK)) {
				if (dCache[index][0].isDirty()) {
					for (int i = 0; i < l / 16; i++) {
						updateMemoryAndCaches(index, i, currentTime);
					}
				}
			}
			int deltaAddress = temp - baseAddress2;
			int[] value = new int[(l / 16)];
			for (int j = deltaAddress; j < deltaAddress + (l / 16); j++) {
				value[j - deltaAddress] = values[j].getValue();
			}
			addToCache(index, temp, value, currentTime);
			return;
		} else {
			baseAddress = (int) (baseAddress / Math.pow(2, disp));
			int index = baseAddress % (s / l / m);
			for (; index < dCache.length; index += (s / l / m)) {
				if (dCache[index][0] == null) {
					int deltaAddress = temp - baseAddress2;
					int[] value = new int[(l / 16)];
					for (int j = deltaAddress; j < deltaAddress + (l / 16); j++) {
						value[j - deltaAddress] = values[j].getValue();
					}
					addToCache(index, temp, value, currentTime);
					return;
					// return value[address-temp];
				}
			}
			index = baseAddress % (s / l / m);
			int newIndex = setAssociativeLRU(index);
			if (writePolicy.equals(WRITE_BACK)) {
				if (dCache[newIndex][0].isDirty()) {
					for (int i = 0; i < l / 16; i++) {
						updateMemoryAndCaches(newIndex, i, currentTime);
					}
				}
			}
			int deltaAddress = temp - baseAddress2;
			int[] value = new int[(l / 16)];
			for (int j = deltaAddress; j < deltaAddress + (l / 16); j++) {
				value[j - deltaAddress] = values[j].getValue();
			}
			addToCache(newIndex, temp, value, currentTime);
			return;
		}

	}

	/**
	 * Updates the value in L1 cache from L2 cache. Used when read miss happens
	 * in L2 cache or L3 cache.
	 * 
	 * @param address
	 *            the address used to read.
	 * @param baseAddress2
	 *            the base address of the address in L2 cache.
	 * @param values
	 *            the values to be updated by. Returned from L2 cache.
	 * @param currentTime
	 *            the current time the operation is performed.
	 */
	public void updateFromL2ICache(int address, int baseAddress2,
			CacheEntry[] instructions, long currentTime) {
		int baseAddress = (int) (address - address % Math.pow(2, disp)); // The
																			// base
																			// address
																			// is
																			// modified
																			// in
																			// the
																			// code
																			// below
		int temp = baseAddress; // Stored in temp value to be used as the
								// original base address
		if (m == 1) {
			int disp = (Log.log(l / 16));
			baseAddress = (int) (baseAddress / Math.pow(2, disp));
			int index = baseAddress % (s / l);
			int deltaAddress = temp - baseAddress2;
			Instruction[] instruction = new Instruction[(l / 16)];
			for (int i = deltaAddress; i < deltaAddress + (l / 16); i++) {
				instruction[i - deltaAddress] = instructions[i]
						.getInstruction();
			}
			addToICache(index, temp, instruction, currentTime);
			return;
		} else if (m == s / l) {
			for (int i = 0; i < iCache.length; i++) {
				if (iCache[i][0] == null) {
					int deltaAddress = temp - baseAddress2;
					Instruction[] instruction = new Instruction[(l / 16)];
					for (int j = deltaAddress; j < deltaAddress + (l / 16); j++) {
						instruction[j - deltaAddress] = instructions[j]
								.getInstruction();
					}
					addToICache(i, temp, instruction, currentTime);
					return;
				}
			}
			int index = LRUI();
			int deltaAddress = temp - baseAddress2;
			Instruction[] instruction = new Instruction[(l / 16)];
			for (int j = deltaAddress; j < deltaAddress + (l / 16); j++) {
				instruction[j - deltaAddress] = instructions[j]
						.getInstruction();
			}
			addToICache(index, temp, instruction, currentTime);
			return;
		} else {
			baseAddress = (int) (baseAddress / Math.pow(2, disp));
			int index = baseAddress % (s / l / m);
			for (; index < iCache.length; index += (s / l / m)) {
				if (iCache[index][0] == null) {
					int deltaAddress = temp - baseAddress2;
					Instruction[] instruction = new Instruction[(l / 16)];
					for (int j = deltaAddress; j < deltaAddress + (l / 16); j++) {
						instruction[j - deltaAddress] = instructions[j]
								.getInstruction();
					}
					addToICache(index, temp, instruction, currentTime);
					return;
				}
			}
			index = baseAddress % (s / l / m);
			int newIndex = setAssociativeLRUI(index);
			int deltaAddress = temp - baseAddress2;
			Instruction[] instruction = new Instruction[(l / 16)];
			for (int j = deltaAddress; j < deltaAddress + (l / 16); j++) {
				instruction[j - deltaAddress] = instructions[j]
						.getInstruction();
			}
			addToICache(newIndex, temp, instruction, currentTime);
			return;
		}

	}

	/**
	 * Read miss in L1 Cache, which get the value from the memory and updates
	 * the L1 Cache (This is called only if one level cache).
	 * 
	 * @param address
	 *            the address of the instruction to be read from the memory.
	 * @param currentTime
	 *            the time at which the operation is performed
	 * @return the instruction read from the memory.
	 */
	public Instruction readMissICache(int address, long currentTime) {
		// The base address is modified in the code below
		int baseAddress = (int) (address - address % Math.pow(2, disp)); 
		Instruction[] instruction = new Instruction[l / 16];
		for (int i = 0; i < instruction.length; i++)
			instruction[i] = Memory
					.loadInstructionUsingAbsoluteAddress(baseAddress + i);
		int temp = baseAddress; // Stored in temp value to be used as the
								// original base address
		if (m == 1) {
			int disp = (Log.log(l / 16));
			baseAddress = (int) (baseAddress / Math.pow(2, disp));
			int index = baseAddress % (s / l);
			addToICache(index, temp, instruction, currentTime);
			return instruction[address - temp];
		} else if (m == s / l) {
			for (int i = 0; i < iCache.length; i++) {
				if (iCache[i][0] == null) {
					addToICache(i, temp, instruction, currentTime);
					return instruction[address - temp];
				}
			}
			int index = LRUI();
			addToICache(index, temp, instruction, currentTime);
			return instruction[address - temp];
		} else {
			baseAddress = (int) (baseAddress / Math.pow(2, disp));
			int index = baseAddress % (s / l / m);
			for (; index < iCache.length; index += (s / l / m)) {
				if (iCache[index][0] == null) {
					addToICache(index, temp, instruction, currentTime);
					return instruction[address - temp];
				}
			}
			index = baseAddress % (s / l / m);
			int newIndex = setAssociativeLRUI(index);
			addToICache(newIndex, temp, instruction, currentTime);
			return instruction[address - temp];
		}

	}

	/**
	 * Updates the values in the caches.
	 * @param cacheLine the line in L1 cache that should update the caches and memory.
	 * @param indexInCacheLine the starting place in the line from which the data should be read.
	 * @param currentTime the current time in which the operation is performed.
	 */
	private void updateMemoryAndCaches(int cacheLine, int indexInCacheLine,
			long currentTime) {
		int address = dCache[cacheLine][indexInCacheLine].getAddress();
		int value = dCache[cacheLine][indexInCacheLine].getValue();
		Memory.store(address, value);
		if (l2 != null) {
			l2.updateValue(address, value, currentTime);
		}
		if (l3 != null) {
			l3.updateValue(address, value, currentTime);
		}
	}

	/**
	 * Sorts the Cache according to the least recently used.
	 * @return
	 */
	private int LRU() {
		Arrays.sort(dCache);
		return 0;
	}
	
	private int LRUI() {
		Arrays.sort(iCache);
		return 0;
	}

	public String getWritePolicy() {
		return writePolicy;
	}

	public void setWritePolicy(String writePolicy) {
		this.writePolicy = writePolicy;
	}

	public int getCycles() {
		return cycles;
	}

	public void setCycles(int cycles) {
		this.cycles = cycles;
	}

	public int getM() {
		return m;
	}

	public void setM(int m) {
		this.m = m;
	}

	public int getS() {
		return s;
	}

	public void setS(int s) {
		this.s = s;
	}

	public int getL() {
		return l;
	}

	public void setL(int l) {
		this.l = l;
	}

	public int getMemAddSize() {
		return memAddSize;
	}

	public void setMemAddSize(int memAddSize) {
		this.memAddSize = memAddSize;
	}

	public L2Cache getL2() {
		return l2;
	}

	public void setL2(L2Cache l2) {
		this.l2 = l2;
	}

	public L3Cache getL3() {
		return l3;
	}

	public void setL3(L3Cache l3) {
		this.l3 = l3;
	}

	public String toString() {
		String x = "";
		x += "------------------Instructions Cache-------------------------\n";
		for (int i = 0; i < iCache.length; i++) {
			x += "Index: " + i + " ";
			for (int j = 0; j < iCache[i].length && iCache[i][j] != null; j++) {
				if(iCache[i][j].getInstruction()!= null)
				x +=  iCache[i][j].getInstruction().shortToString() + " | ";
			}
				x += "\n";
		}
		
		x += "------------------Data Cache-------------------------\n";
		for (int i = 0; i < dCache.length; i++) {
			x += "Index: " + i + " ";
			for (int j = 0; j < dCache[i].length && dCache[i][j] != null; j++) {
				x +=  dCache[i][j].toString() + " | ";
			}
			
				x += "\n";
		}
		return x;
	}
}
